The present invention relates generally to wireless, packet-hopping networks, and more particularly, to a method of routing data packets within such a network, and to a wireless network for implementing the same.
A network which consists of a plurality of nodes which communicate with each other and with a central node via wireless (RF) links is generally referred to as a wireless (or radio) network. In such wireless networks, each node includes a digital signal processing device (e.g., a microprocessor) and an RF transceiver which has a prescribed transmitting range. Data is typically communicated (transferred) between the individual nodes and the central node by a technique known as "packet hopping", in which individual packets of data are transferred from the central node to a destination node and from an origin node to the central node by being hopped from node-to-node in accordance with a network routing protocol.
"Packets" are logical units of data typically ranging in size from about 5-1000 bytes. Generally, these packet-hopping data communications are under the control of the central node, which is usually a computer on which resides the data communications control software. The packet-hopping data transfer scheme enables a reduction in the cost of the RF transceivers and compliance with FCC Part 15 requirements. Each packet of data contains the address of the node from which it originated or is destined. The address of each node is established when the network is originally installed.
Such wireless, packet-hopping networks are particularly suitable for controlling one or more functions or systems of a building, e.g., the lighting, HVAC, and/or security systems of the building, because it offers a low-cost, indoor topology that does not require new lines to be added to the existing structure in order to carry the network information. Further, such networks could support additional systems installed in the building, such as paging and personal communications systems.
The central node of such building control networks is typically a programmable central controller or building computer on which resides the system control software. The individual nodes are typically distributed throughout the building to monitor the status/value of prescribed parameters of the building system being controlled, and to produce control signals in response to commands issued by the building computer to adjust such parameters as required. It is important that the building computer be able to send and receive data to and from each node in the network in order to properly monitor the status/value of such prescribed parameters, and to issue commands to adjust such parameters as required, in accordance with the system control software.
An exemplary building control network is an automatic or intelligent lighting control system which monitors lighting levels, occupancy status, energy consumption as a function of time, and/or other lighting parameters of each room and/or area of the building within the network, i.e., each room and/or area of the building which is equipped with a lighting module(s) linked to an RF transceiver which constitutes a node in the network under the control/management of the building computer.
In such an intelligent lighting control system, each of the lighting modules is preferably individually programmable (e.g., by building occupants) to provide direct control of the lighting level of the lamps associated therewith. In this regard, each of the lighting modules includes one or more sensors (e.g., occupancy status, daylight (ambient lighting), and dimming/lighting level sensors) which provide sensor feedback data to an onboard digital signal processing device (e.g., a microprocessor) which is programmed to analyze the sensor feedback data and to generate control signals for adjusting the lighting level of the monitored lamp(s) associated therewith, as required, to achieve the programmed local lighting conditions.
This sensor feedback data is also transmitted by each node in the network to the building computer, when requested by the building computer to do so, or when the local lighting conditions change. The building computer analyzes such sensor feedback data in accordance with lighting system control software loaded therein, and sends control data (commands) to the individual nodes, as required, in order to adjust the lighting levels of the monitored rooms/areas of the building in accordance with the lighting system control software, e.g., to optimize the energy efficiency of the lighting system, and thereby override the programmed lighting levels provided by the individual lighting modules. Thus, in addition to being individually programmable and being capable of independent operation, the distributed modules are functionally integrated into a single building-wide network under the control of the building computer.
The installation of a building control network entails the physical placement and powering of each node in the network. The address of each node in the network can either be programmed into the node at installation or, if preprogrammed, logged into the memory of the central node (building computer), along with the physical location of each node in the network. Data communications in such networks are generally between the building computer and the individual nodes, and vice versa, over a common communications channel, in accordance with a network routing protocol. The data is transferred in packets from the building computer to a destination node outside of the immediate transmitting range of the building computer (i.e., not directly linked or "connected" to the building computer) by hopping or relaying each packet from node-to-node until the packet reaches the destination node. Each of the nodes which hops or relays a packet to one or more other nodes in the network is commonly referred to as a "repeater". The destination node generally acknowledges receipt of a data packet from the building computer by returning an acknowledgement data packet to the building computer via one or more repeaters in a similar fashion.
There are generally two main categories of network routing algorithms or protocols that are utilized in wireless networks, namely, random and deterministic (tabular) routing protocols. With a random routing protocol, packets are randomly hopped through the nodes in the network from a sender node to a destination node along random routes, with no specific set of repeaters being used to effectuate the data transfer. More particularly, with the random routing protocol, the sender node transmits a packet to all nodes within its transmitting range and each node which receives the packet then re-transmits or relays the packet to every node within its respective transmitting range, and so on, until the packet reaches the destination node. Typically, each packet contains a byte commonly called the "hop counter", which is decremented by each repeater until it reaches zero. Once it reaches zero, the packet is no longer repeated. The hop counter is set by the sending (transmitting) node such that the probability that the packet reaches the destination node is maximized, without dominating the network for an unduly lengthy period of time.
In order to minimize simultaneous transmissions of packets over the common network channel, a channel access protocol is utilized. The most common channel access protocol is the carrier sense multiple access (CSMA) protocol, according to which each node, prior to transmitting a packet, waits for a random delay period, and then senses the channel to determine whether it is available ("clear") or unavailable ("busy"). If the channel is sensed to be clear it transmits the packet, and if the channel is sensed to be busy, it waits for another random delay period before sensing the status of the channel again before making a further attempt to transmit the packet.
However, since all nodes in the network are not within the "listening range" of each other, it frequently occurs that two nodes which are outside of each other's listening range will sense that the channel is clear and transmit respective packets which overlap in time to the same receiving node, thereby resulting in corruption of both data packets, which appear as noise to the receiving node. This phenomenon is generally referred to as an "unavoidable or unresolvable collision". With the random routing protocol, there is a rather high probability that most, if not all, nodes in the network will handle each and every packet transmitted, thereby greatly increasing the data traffic density in the network, and thus, greatly limiting the number of different packets which can be "on the network" at any given time (i.e., the data traffic handling capacity of the network). This limits the communication efficiency of the network, as well as increasing the number of unresolvable collisions which occur.
These unresolvable collisions of data packets can cause packets to be lost before they reach their destination. In this connection, in building control networks, the acknowledgement packets returned to the building computer typically converge on just a few nodes that are linked to the building computer, thereby resulting in a higher probability and greater number of unresolvable collisions involving such packets. Consequently, blockage of acknowledgement packets is common, thereby forcing the building computer to re-transmit a packet in order to determine whether the original packet sent was actually received by the destination node.
According to the deterministic or tabular routing protocol, the building computer formulates routing tables on the basis of nodal connectivity information which it gathers during execution of a network initialization routine. These routing tables are then used to route packets of data from a sender node to a destination node via a specific set or "chain" of repeaters (i.e., along a predetermined route or singular path defined in the routing tables). This allows for many different packets to be "on the network" simulaneously, thereby resulting in relatively higher network data traffic handling capacity than is possible with the random routing protocol. However, because of intrinsic RF constraints of wireless networks, the deterministic routing protocol severely limits the communication efficiency of the network, thereby resulting in a relatively low probability of a given packet being able to reach its destination, due to its being routed along a single, predetermined path, as opposed to multiple random paths (as with the random routing protocol).
In this regard, the reliability of node-to-node communications in indoor, wireless networks is adversely affected by phenomena such as fading and multipath (the interference of an RF signal with itself due to reflections off surfaces such as walls, floors, ceilings, furniture, etc.), whereby previously established node-to-node links can be interrupted or lost. Further, such previously established node-to-node links can be interrupted or lost by virtue of dynamic changes in the indoor environment of the building, such as certain activities of the building occupants. For example, the simple action of opening or closing or door, moving furniture, or even walking down a hallway can disrupt a node-to-node communication link. Thus, the status of any given node-to-node link within the network may vary over time from solid, to sporadic, to non-existent, depending upon a number of largely unpredictable and uncontrollable variables.
Because of these inherent link reliability problems, data packets transmitted along a singular path can be easily lost before they reach their destination, thus requiring such data packets to be re-transmitted, thereby degrading the communications efficiency of the network. All that is required for a transmission to be unsuccessful is for a single link in the chain of repeaters to be broken either on the outbound transmission of a command data packet from the building computer to the destination node, or on the inbound transmission of the acknowledgement data packet from the destination node to the building computer. If the link quality of the problemmatic link(s) is not resolved satisfactorily, then the packet may have to be re-routed, and/or the network reconfigured, thereby further degrading the performance of the network, and increasing its cost and complexity.
A deterministic routing algorithm which incorporates reconfigurability is certainly an improvement over standard deterministic routing algorithms. Such a deterministic routing algorithm is disclosed in co-pending U.S. patent application Ser. No. 08/558,447, filed Nov. 16, 1995, in the name of A. Dasgupta and assigned to the assignee of the present invention, the disclosure of which is herein incorporated by reference. However, such a routing algorithm still requires the attention of the operator or some preprogrammed handling routine (typically executed by the building computer) which can identify the faulty link or leg of the route, and program a route around it. Such re-routing can be extremely time-consuming and entirely unwarranted if the blockage being experienced is temporary. Furthermore, the new path may be no better than the previous path. This algorithm may also require that a significant portion of the routing information be contained in the data packets, thereby increasing the size of such packets, and, consequently, further reducing the data traffic handling capacity and communication efficiency of the network.
There are various known ways to address the above-described link reliability problems. One way to improve link reliability is to use higher-powered RF transceivers, and another way to improve link reliability is to use noise-limiting spread spectrum transceivers. However, both of these approaches are generally cost-prohibitive for many applications. Of course, a hard-wired network would be an ideal solution, but the cost of installing such a network in an existing structure is cost-prohibitive for most applications.
Based on the above and foregoing, it can be appreciated that there presently exists a need in the art for a method for routing packets in a wireless, packet-hopping network which overcomes the above-described drawbacks, shortcomings, and disadvantages of the presently available technology. The present invention fulfills this need in the art.